/*
 * @lc app=leetcode.cn id=15 lang=golang
 *
 * [15] 三数之和
 */

// @lc code=start

//二分法查找
//切片s是升序的
//k为待查找的整数
//如果查到有就返回对应角标,
//没有就返回-1
func BinarySearch(s []int, k int) int {
	lo, hi := 0, len(s)-1
	for lo <= hi {
		m := (lo + hi) >> 1
		if s[m] < k {
			lo = m + 1
		} else if s[m] > k {
			hi = m - 1
		} else {
			return m
		}
	}
	return -1
}

func threeSum(nums []int) [][]int {
	var result [][]int = [][]int{}
	var length = len(nums)
	if length < 3 {
		return result
	}
	sort.Ints(nums)
	// 判断是否有3个0
	for i := 0; i < length; i++ {
		if nums[i] == 0 {
			if i+2 < length && nums[i+2] == 0 {
				result = append(result, []int{0, 0, 0})
			}
			break
		}
	}
	if nums[0] >= 0 || nums[length-1] <= 0 {
		return result
	}
	var left, right []int
	var zeroFlag, reapFalg bool
	var reap []int = make([]int, 5)
	{
		var idx, i, t int = 1, 1, nums[0]
		for ; i < length && nums[i] < 0; i++ {
			if nums[i] != t {
				if i != idx {
					nums[idx] = nums[i]
				}
				t = nums[idx]
				reapFalg = false
				idx++
			} else if !reapFalg {
				reap = append(reap, t)
				reapFalg = true
			}
		}
		// 置位
		reapFalg = false
		left = nums[0:idx]
		zeroFlag = nums[i] == 0
		i = len(nums) - 2
		idx, t = i, nums[i+1]
		for ; nums[i] > 0; i-- {
			if nums[i] != t {
				if i != idx {
					nums[idx] = nums[i]
				}
				t = nums[idx]
				reapFalg = false
				idx--
			} else if !reapFalg {
				reap = append(reap, t)
				reapFalg = true
			}
		}
		right = nums[idx+1:]
	}

	var lf, lr = len(left), len(right)
	if zeroFlag {
		var l, r int = len(left) - 1, 0
		for r < lr && l >= 0 {
			lv := -left[l]
			if lv == right[r] {
				result = append(result, []int{left[l], 0, right[r]})
				l--
				r++
			} else if lv > right[r] {
				r++
			} else {
				l--
			}
		}
	}
	for _, v := range reap {
		if v > 0 {
			idx := BinarySearch(left, -v-v)
			if idx != -1 {
				result = append(result, []int{left[idx], v, v})
			}
		} else {
			idx := BinarySearch(right, -v-v)
			if idx != -1 {
				result = append(result, []int{v, v, right[idx]})
			}
		}
	}
	for i := lf - 1; i >= 0; i-- {
		for j := i - 1; j >= 0; j-- {
			v := -left[i] - left[j]
			idx := BinarySearch(right, v)
			if idx != -1 {
				result = append(result, []int{left[j], left[i], right[idx]})
			}
		}
	}
	for i := 0; i < lr; i++ {
		for j := i + 1; j < lr; j++ {
			v := -right[i] - right[j]
			idx := BinarySearch(left, v)
			if idx != -1 {
				result = append(result, []int{left[idx], right[i], right[j]})
			}
		}
	}
	return result
}

// @lc code=end

